/************************************************************
 * DS_NAMED_PAIR.H                                 10.12.2007
 *
 * .
 ************************************************************/
#ifndef _DS_NAMED_PAIR_H_
#define _DS_NAMED_PAIR_H_

#pragma once

#include "ds_allocator.h"

namespace ds {

template <class K, class V, class H, class C, template <class AT> class A>
class MAP;

template <class L, class R>
struct NAMED_PAIR : public L, public R {
	NAMED_PAIR(void) {}

	template <class TL, class TR>
	NAMED_PAIR(const TL & tl, const TR & tr)
		: L(tl), R(tr)
	{}

	template <class TL, class TR, class TR2>
	NAMED_PAIR(const TL & tl, const TR & tr, const TR2 & tr2)
		: L(tl), R(tr, tr2)
	{}

	template <class TL, class TR, class TR2, class TR3>
	NAMED_PAIR(const TL & tl, const TR & tr, const TR2 & tr2, const TR3 & tr3)
		: L(tl), R(tr, tr2, tr3)
   {}

	bool operator < (const NAMED_PAIR<L, R> & p) const {
		return (static_cast<const L &> (*this) < p) ||
			(static_cast<const L &> (*this) == p) && (static_cast<const R &> (*this) < p);
   }

	bool operator == (const NAMED_PAIR<L, R> & p) const {
		return (static_cast<const L &> (*this) == p) && (static_cast<const R &> (*this) == p);
   }
};

} // namespace ds

#define dsNAMED_PAIR_DECL(NAME) \
   namespace ds { \
      template <class T> \
      struct NAMED_PAIR_##NAME { \
         NAMED_PAIR_##NAME(void) : NAME() {} \
         NAMED_PAIR_##NAME(const T & NAME) : NAME(NAME) {} \
         bool operator < (const NAMED_PAIR_##NAME & p) const { return NAME < p.NAME; } \
         bool operator == (const NAMED_PAIR_##NAME & p) const { return NAME == p.NAME; } \
         T & Value(void) { return NAME; } \
         const T & Value(void) const { return NAME; } \
         T NAME; \
      }; \
   }

#define dsNAMED_PAIR_T(TYPE1, NAME1, TYPE2, NAME2) \
   ds::NAMED_PAIR<ds::NAMED_PAIR_##NAME1<TYPE1>, ds::NAMED_PAIR_##NAME2<TYPE2> >

#define dsNAMED_PAIR3_T(TYPE1, NAME1, TYPE2, NAME2, TYPE3, NAME3) \
	ds::NAMED_PAIR<ds::NAMED_PAIR_##NAME1<TYPE1>, dsNAMED_PAIR_T(TYPE2, NAME2, TYPE3, NAME3)>

#define dsNAMED_PAIR4_T(TYPE1, NAME1, TYPE2, NAME2, TYPE3, NAME3, TYPE4, NAME4) \
	ds::NAMED_PAIR<ds::NAMED_PAIR_##NAME1<TYPE1>, dsNAMED_PAIR3_T(TYPE2, NAME2, TYPE3, NAME3, TYPE4, NAME4)>

// just several names
dsNAMED_PAIR_DECL(id);
dsNAMED_PAIR_DECL(name);
dsNAMED_PAIR_DECL(type);
dsNAMED_PAIR_DECL(weight);
dsNAMED_PAIR_DECL(obj);
dsNAMED_PAIR_DECL(count);
dsNAMED_PAIR_DECL(value);
dsNAMED_PAIR_DECL(file);
dsNAMED_PAIR_DECL(line);
dsNAMED_PAIR_DECL(ptr);
dsNAMED_PAIR_DECL(size);
dsNAMED_PAIR_DECL(length);
dsNAMED_PAIR_DECL(dist);
dsNAMED_PAIR_DECL(distance);
dsNAMED_PAIR_DECL(buffer);
dsNAMED_PAIR_DECL(item);
dsNAMED_PAIR_DECL(key);
dsNAMED_PAIR_DECL(key1);
dsNAMED_PAIR_DECL(key2);
dsNAMED_PAIR_DECL(node);
dsNAMED_PAIR_DECL(found);
dsNAMED_PAIR_DECL(parent);
dsNAMED_PAIR_DECL(child);
dsNAMED_PAIR_DECL(left);
dsNAMED_PAIR_DECL(right);
dsNAMED_PAIR_DECL(next);
dsNAMED_PAIR_DECL(prev);
dsNAMED_PAIR_DECL(pos);
dsNAMED_PAIR_DECL(dir);
dsNAMED_PAIR_DECL(color);
dsNAMED_PAIR_DECL(info);
dsNAMED_PAIR_DECL(index);
dsNAMED_PAIR_DECL(state);
dsNAMED_PAIR_DECL(flags);
dsNAMED_PAIR_DECL(wasReplaced);
dsNAMED_PAIR_DECL(first);
dsNAMED_PAIR_DECL(second);
dsNAMED_PAIR_DECL(start);
dsNAMED_PAIR_DECL(end);
dsNAMED_PAIR_DECL(callback);
dsNAMED_PAIR_DECL(data);
dsNAMED_PAIR_DECL(list);
dsNAMED_PAIR_DECL(x);
dsNAMED_PAIR_DECL(y);
dsNAMED_PAIR_DECL(z);

namespace ds {

template <class T>
class NAMED_HELPER;

template <class Type1, template <class> class Name1, class Type2, template <class> class Name2>
class NAMED_HELPER<NAMED_PAIR<Name1<Type1>, Name2<Type2> > > {
public:
   typedef NAMED_PAIR<Name1<Type1>, Name2<Type2> >    PAIR_T;
   typedef dsVECTOR<PAIR_T>                           ARRAY_T;
   typedef ds::MAP<Type1, Type2, HASH, CMP, dsNODE_CACHE_ALLOCATOR> MAP_T;

   typedef ds::MAP<Type2, int, HASH, CMP, dsNODE_CACHE_ALLOCATOR> VALUE_COUNT_MAP_T;
   typedef NAMED_HELPER<NAMED_PAIR<NAMED_PAIR_count<int>, Name2<Type2> > > COUNT_VALUE_HELPER_T;
   typedef NAMED_HELPER<NAMED_PAIR<Name2<Type2>, NAMED_PAIR_count<int> > > VALUE_COUNT_HELPER_T;

   static void MakePairArray(const MAP_T & map, ARRAY_T & array, bool sortArray = true) {
      for (typename MAP_T::const_iterator iter = map.Begin(); !iter.IsDone(); ++iter) {
         array += PAIR_T(iter.key(), iter.value());
      }

      if (!sortArray) {
         ds::Sort(array);
      }
   }

   static void MakeValueCountMap(const MAP_T & map, VALUE_COUNT_MAP_T & vcMap) {
      for (typename MAP_T::const_iterator iter = map.Begin(); !iter.IsDone(); ++iter) {
         ++vcMap.FindInsert(iter.value()).value();
      }
   }

   static void MakeCountValueArray(const MAP_T & map, typename COUNT_VALUE_HELPER_T::ARRAY_T & array) {
      VALUE_COUNT_MAP_T vcMap;
      MakeValueCountMap(map, vcMap);

      for (typename VALUE_COUNT_MAP_T::const_iterator iter = vcMap.Begin(); !iter.IsDone(); ++iter) {
         array += typename COUNT_VALUE_HELPER_T::PAIR_T(iter.value(), iter.key());
      }

      ds::Sort(array);
   }

   static void MakeValueCountArray(const MAP_T & map, typename VALUE_COUNT_HELPER_T::ARRAY_T & array) {
      VALUE_COUNT_MAP_T vcMap;
      MakeValueCountMap(map, vcMap);

      for (typename VALUE_COUNT_MAP_T::const_iterator iter = vcMap.Begin(); !iter.IsDone(); ++iter) {
         array += typename VALUE_COUNT_HELPER_T::PAIR_T(iter.value(), iter.key());
      }

      ds::Sort(array);
   }
};

} // namespace ds

#define dsNAMED_HELPER_T(TYPE1, NAME1, TYPE2, NAME2) \
   ds::NAMED_HELPER< dsNAMED_PAIR_T(TYPE1, NAME1, TYPE2, NAME2) >

template <class N1, class N2>
int Hash(const ds::NAMED_PAIR<N1, N2> & p)
{ return Hash(static_cast<const N1 &> (p).Value()) + Hash(static_cast<const N2 &> (p).Value()); }

template <class N1, class N2>
UINT Hash(const ds::NAMED_PAIR<N1, N2> & p, UINT a, UINT b)
{ return Hash(static_cast<const N1 &> (p).Value(), a, b) + Hash(static_cast<const N2 &> (p).Value(), a, b); }

#endif // _DS_NAMED_PAIR_H_
